Mixed integer programming is a widely accepted method in formulating and optimizing complex business, engineering or any complex discrete optimization problems. Mixed integer programming is a modeling language of optimization, which is general enough to cover a very wide range of optimization problems, however due to its mathematical nature most of the unsolved problems that impede the spread of GRID, cluster and desktop GRID networks can be handled. The current peer-to-peer (P2P) networks may connect an extremely high number of public computers with very heterogeneous computational performance. Mixed-integer program is a restricted form of mathematical program (see A. Holder, editor. Mathematical Programming Glossary. INFORMS Computing Society, http://glossary.computing.society.informs.org/, 2006-2007. Originally authored by Harvey J. Greenberg, 1999-2006, incorporated herein by reference), where some of the variables are required to be integer-valued. Note that, in prior art publications this term implied the mathematical program was otherwise linear. The definition of Mixed-integer programs (MIP) used in the present invention is the following:MIP:Minƒ(x)g(x)≧0
where x are the decision variables (some of or all of the decision variables can take only integer solution), ƒ is a real valued objective function that is a mathematical function on the decision variables, and g are real-valued functions, called constraints. The goal of optimization is to find values for each decision variable such that the objective function is minimal. There are three main groups of MIP:                a. MILP: Mixed integer linear program, where the constraints and the object function are functions of x.        b. MINLP: Mixed integer nonlinear program, where the constraints and the object function can be any functions of x.        c. MIQP: Mixed integer quadratic program, where the constraints are linear functions of x and the object function is in the form of xTQx+cTx.        
In terms of complexity all of these problems belong to the NP-hard class, and thus with Karp-reduction the problems can be reduced to each other. Their classical solution method is a tree-search branch-and-bound algorithm in which each tree node represents a program, where the integer constraints are eliminated (called relaxed problem).
The present invention, in one aspect thereof, deals with mixed integer programs that are solved by branch-and-bound or branch-and-cut algorithms.
Solving MIP with Branch and Bound (BB) Algorithm
The branch and bound (BB) algorithm is a recursive search method, where in each step of the recursion the solution space is partitioned into several smaller sub-problems that are either solved or further partitioned into smaller sub-problems in the next step of the recursion. During the recursions a searching tree (called BB tree) is built up until all sub-problems are solved. In MIP solvers each node of the search tree is itself an MIP problem. In the bounding phase, the MIP problem of the node is relaxed (integer constraints are relaxed to simple bound constraints) and the relaxed problem is solved (see Ralph Edward Gomory and Ellis Lane Johnson, “Data Processing System For Finding Optimum Integer-Valued Solutions Of Linear Programs”, Great Britain Patent Application GB19720007853, Aug. 7, 1974; Mehrotra; Sanjay; et al., “Generalized branching methods for mixed integer programming”, United States Patent Application 20060112049, May 25, 2006; T. K. R., L. Ladányi, and M. J. Saltzman, “Parallel Branch, Cut, and Price for Large-scale Discrete Optimization”, Mathematical Programming 98 (2003), 253, incorporated herein by reference). Obviously, the solution of the relaxed problem is a lower bound on the solution of the corresponding MIP. Any feasible integer solution is an upper bound on the cost of the original MIP. The feasible integer solution might be derived from the solution of the relaxed problem with some state-of-the-art heuristics.
In the branching phase, first the solution is tested to determine if the integer constraints can be satisfied. If there is any variable that violates the integer constraints, it is selected to generate two sub-problems in the branching phase each with an extra constraint that precludes the current infeasible solution. Formally, if the integer variable x has a non-integer solution f the constraint x≦└f┘ x≧┌f┐ is added to the original MIP problem forming the two new sub-problems. In such a way all integer solutions are feasible in one of the sub-problems. Obviously branching generates an exponential number of sub-problems that need to be processed in order to solve the original problem. Sub-problems can be discarded (or fathomed) if (1) the sub-problem has an integer solution, (2) the sub-problem is infeasible, or (3) the linear sub-problem has worse objective value than a currently available best integer solution (bounding) (see Qun Chen, Michael Ferris and Jeff Linderoth, “FATCOP 2.0: Advanced features in an opportunistic mixed integer programming solver”, Data Mining Institute Technical Report 99-11, Computer Sciences Department, University of Wisconsin, Madison, Wis., 1999, incorporated herein by reference). Every sub-problem, which can not be fathomed and was not solved needs to be processed later, and are each called active nodes of the search tree.
Mixed Integer Linear Program (MILP)
Mixed Integer Linear Program is known for its flexibility in formulating combinatorial optimization problems. MILP solvers can solve a great selection of algorithmic problems, even NP-complete (intractable) ones. Obviously the runtime of the MILP solver is thus exponential compared to the size of input. A MILP consists of a Linear Program (LP), which is the minimization of a linear function subject to linear constraints, and some or all of the variables should be integer. Any LP can be solved efficiently (in polynomial computational time). In the MILP solvers LP-based branch and bound algorithms are implemented.
The efficiency of LP-based branch and bound strongly depends on the gap between the solution of the MILP and the relaxed problem (See Ralph Edward Gomory and Ellis Lane Johnson, “Data Processing System For Finding Optimum Integer-Valued Solutions Of Linear Programs”, Great Britain Patent Application GB19720007853, Aug. 7, 1974; Mehrotra; Sanjay; et al., “Generalized branching methods for mixed integer programming”, United States Patent Application 20060112049, May 25, 2006; T. K. R., L. Ladányi, and M. J. Saltzman, “Parallel Branch, Cut, and Price for Large-scale Discrete Optimization”, Mathematical Programming 98 (2003), 253, incorporated herein by reference). The gap is small if the relaxation is tight and the relaxed constraints closely approximate the feasible integer region. The LP relaxations can be tightened by adding inequalities (called cutting planes) that are valid for the original MILP. To improve the efficiency of branch and bound algorithms, they are usually combined with cutting plane methods (and called branch and cut) (See T. K. R., L. Ladányi, and M. J. Saltzman, “Parallel Branch, Cut, and Price for Large-scale Discrete Optimization”, Mathematical Programming 98 (2003), 253).
Distributed Systems (GRIDS, P2P, Desktop GRIDS)
Solving computationally very complex problems requires parallel algorithms, run on several computers. Today computer clusters are mainly used for mass computation which consists of a few tens (or hundreds) of private high-performance computers. Cluster computers are mainly designed to work on single (or very few) problems in a parallel manner and, thus, balancing the load among the computers is the key challenge. GRID computers are similar to cluster but geographically distributed, allowing much more high performance computers to be involved. GRID computers are also widely used, providing mass computational power. They key disadvantage of GRID and cluster networks is the difficulty in providing a general tool for parallelizing algorithms, and maintaining a reliable trusted environment for parallel computing.
Another alternative is desktop GRID which tries to utilize the PCs idle cycles around the globe to provide powerful distributed system. Such projects (like Entropia™ network (see A. A. Chien, B. Calder, S. Elbert, and K. Bhatia, “Entropia: architecture and performance of an enterprise desktop grid system,” Journal of Parallel and Distributed Computing, vol. 63, no. 5, pp. 597-610, 2003, incorporated herein by reference), SETI@Home™ (see Berkeley Open Infrastructure for Network Computing, url: http://boinc.berkeley.edu/, incorporated herein by reference), Folding@Home™ (see Folding@home distributed computing project, url: http://folding.stanford.edu/English/Main, incorporated herein by reference), Parabon's™ Compute-Against-Cancer™ (see Compute Against Cancer program, url: http://www.parabon.com/cac.jsp, incorporated herein by reference), and FightAIDSHome™ (see Fight AIDS At Home Computer Project, url: http://fightaidsathome.scripps.edu/, incorporated herein by reference)) are designed to solve special problems in an offline manner. These desktop GRIDs are based on the unselfish Internet community donating their idle computational power for research purposes. Humans are mainly used to parallelize the algorithms for desktop GRID, unless the GRIDs are not designed for a very specific type of calculation. Although desktop GRID has achieved enormous computational power, currently the computational time of each job takes much more time than any business-like computational application can tolerate. For example, Folding@Home has achieved more than 1000 teraflops at January 2008, which are 1015 floating point operations per second. Following the success of desktop GRID it must be assumed there is a distributed, heterogynous public environment; however the goal is rapid problem solving in order to attract business applications, and allow a more powerful usage of world's idle computational power by establishing a market of computational time. In other words the goal is to provide consideration for the computers involved in the computation.
Meanwhile, peer-to-peer (P2P) networks have achieved the connecting of extremely high number of computers. P2P applications are generally lightweight and easy to install, and their protocols can sneak through firewalls and network address translation (NAT). The main advantage of P2P networks over GRID networks is the simplicity of installation and maintenance. A P2P computer network runs at the application layer and all clients provide computing power. The current P2P networks are typically used for connecting nodes via largely ad hoc connections and are mainly used for sharing content files or real-time data (i.e., audio or video streaming).
P2P networks basically have not been used for sharing computational power. Thus there is a need for a system whereby P2P networks are used for a desktop GRID-like network with prompt problem solving.
The present invention addresses this challenge, facilitated by an application called MIP that has market demand, and can be easily parallelized.